13.11 The DSS document includes a recommended algorithm for testing a number for primality, as follows: 1. [Choose w] Let w be a random odd integer. Then (w 1) is even and can be expressed in the form 2a m with m odd. That is, 2a is the largest power of 2 that divides (w 1). 2. [Generate b] Let b be a random integer in the range 1 3. [Exponentiate] Set j = 0 and z = bm mod w. 4. [Done?] If j = 0 and z = 1, or if z = w 1, thenw passes the test and may be prime; go to step 8. 5. [Terminate?] If j > 0 and z = 1, then w is not prime; terminate algorithm for thisw . [Increase j] Set j = j + 1. If j < a, set z = z2 6. mod w and go to step 4. 7. [Terminate]w is not prime; terminate algorithm for thisw . 8. [Test again?] If enough random values of b have been tested, then accept w as prime and terminate algorithm; otherwise, go to step 2. a. Explain how the algorithm works. b. Show that it is equivalent to the Miller-Rabin test described inC hapter 8. | |
| View Solution | |
| << Back | Next >> |